#include <iostream>
using namespace std;

int cnt;

void Merge(int *sz, int p, int q, int r) {
	int n1 = q - p + 1;
	int n2 = r - q;

	int * sz1 = (int*)malloc(sizeof(int)*n1);
	int * sz2 = (int*)malloc(sizeof(int)*n2);

	int i = 0, j = 0, k = 0;
	for (i=0;i<n1;i++)
		sz1[i] = sz[p+i];
	for (j=0;j<n2;j++)
		sz2[j] = sz[q+j+1];

	i = 0; j = 0, k = p;
	while (i<n1 && j<n2) {
		if (sz1[i] <= sz2[j])
			sz[k++] = sz1[i++];
		else {
			cnt = cnt + j;
			sz[k++] = sz2[j++];
		}
	}

	while (i<n1) {
		cnt = cnt + j;
		sz[k++] = sz1[i++];
	}
	while (j<n2)
		sz[k++] = sz2[j++];
}

void MergeSort(int *sz, int p, int r) {
	if (p < r)	{
		int q = (p + r)/2;
		MergeSort(sz, p, q);
		MergeSort(sz, q+1, r);
		Merge(sz, p, q, r);
	}
}

//int main() {
//	cnt = 0;
//	int sz1[] = {2, 3, 8, 6, 1};
//	cnt = 0;
//	MergeSort(sz1, 0, 4);
//
//	cnt = 0;
//	int sz2[] = {1, 4, 2, 9, 48, 15, 13, 44, 6, 90};
//	MergeSort(sz2, 0, 9);
//
//	return 0;
//}

int InversePairCore(int* data, int* copy, int start, int end) {
	if (start == end) {
		copy[start] = data[start];
		return 0;
	}

	int length = (end-start)/2;
	int left = InversePairCore(copy, data, start, start+length);
	int right = InversePairCore(copy, data, start+length+1, end);

	int i = start+length;
	int j = end;
	int indexCopy = end;
	int count = 0;
	while (i>=start && j>=start+length+1) {
		if (data[i] > data[j]) {
			copy[indexCopy--] = data[i--];
			count += j-start-length;
		}
		else
			copy[indexCopy--] = data[j--];
	}
	
	for (; i>=start; i--)
		copy[indexCopy--] = data[i];
	for (; j>=start+length+1; j--)
		copy[indexCopy--] = data[j];

	return left + right + count;
}

int InversePair(int* data, int len) {
	if (data==NULL || len<0)
		return 0;

	int* copy = new int[len];
	memcpy(copy, data, sizeof(int)*len);
	int count = InversePairCore(data, copy, 0, len-1);
	delete [] copy;

	return count;
}

//int main(){
//	int data[] = {7,6,5,4};
//	int count  = InversePair(data, 4);
//	return 0;
//}